package code.oldCode.feishuSpecializedTraining.dynamic;

import java.util.Arrays;

/**
 * @author 26029
 * @date 2025/3/21
 * @description
 */
public class MyDP2 {
    // 62. 不同路径
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int i = 0; i < n; i++) {
            dp[0][i] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }

    // 63. 不同路径 II
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            if (obstacleGrid[i][0] == 1)
                break;
            dp[i][0] = 1;
        }
        for (int i = 0; i < n; i++) {
            if (obstacleGrid[0][i] == 1)
                break;
            dp[0][i] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 1)
                    continue;
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }

    // 416. 分割等和子集
    public boolean canPartition(int[] nums) {
        // 1 <= nums.length <= 200
        // 类背包问题
        // 算出target，然后dp找，找到最大值，如果最大值比目标大，其他数加起来一定没他大，一定没结果
        if (nums.length == 1)
            return false;
        int sum = Arrays.stream(nums).sum();
        int max = Arrays.stream(nums).max().getAsInt();
        if (sum % 2 == 1)
            return false;
        int target = sum / 2;
        if (max > target)
            return false;
        // 背包问题的二维dp数组
        boolean[][] dp = new boolean[nums.length][target + 1]; // dp[i][j]表示前i个数是否有和为j的
        for (int i = 0; i < nums.length; i++) {
            dp[i][0] = true;
        }
        dp[0][nums[0]] = true;
        // 背包问题的两重循环
        for (int i = 1; i < nums.length; i++) {
            for (int j = 1; j <= target; j++) {
                // 如果num<=j，说明要找两种情况，一种是前i-1个已经满足（不选），另一种是前i-1个满足j-num（选）
                if (nums[i] <= j) {
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
                }
                // 如果num>j，说明这个num肯定不能选
                else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[nums.length - 1][target];
    }
}
